#include <stdio.h>

char prime_table[1000005] = {0};
int func_table[1000005] = {0};
int ranges_table[1000005] = {0};

void prepare() {
    prime_table[0] = prime_table[1] = 1;
    for (int i = 2; i < 1010; i == 2 ? (i = 3) : (i += 2)) {
        for (int n = i; n < 1000005; n += i) {
            if (i != n) prime_table[n] = 1;
        }
    }
    
    for (int i = 0; i < 1000005; i++) {
        if (!prime_table[i]) {
            for (int j = i; j < 1000005; j += i) {
                for (
                    int k = j, n = 0;
                    (k % i == 0) || (func_table[j] += n, 0);
                    k /= i, n++
                );
            }
        }
    }
    
    for (int i = 0, n = 0; i < 1000005; i++) {
        ranges_table[i] = (n += func_table[i]);
    }
}

int main(void) {
    prepare();
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", ranges_table[b] - ranges_table[a - 1]);
    }
}
